import java.util.ArrayList;

class BinaryHeapArray<T extends Comparable<T>> extends BinaryHeap<T> {
    //private Vector<T> m_heap;    //Vector synchronizes on each individual operation
                                   //Thats very costly and not what we want to do. 
    private ArrayList<T> m_heap;   //Instead we use ArrayList that is not synchronized
                                   //at all and let the user of BinaryHeapArray manage
                                   //synchronization of sequencies of operations instead
    //Constructor
    public BinaryHeapArray() {
        super(); //Calls constuctor of BinaryHeap
	m_heap = new ArrayList();
    } 
    //Returns if the heap is empty or not
    @Override
    public boolean isEmpty() { return m_heap.isEmpty(); };
    //Returns the size, number of elements (=maxIndex+1), of the heap
    @Override
    public int size() { return m_heap.size(); };
    //Just returns the top (largest value) without modifying the heap 
    @Override
    public T getTop() { 
        if (m_heap.isEmpty()) return null;
	return m_heap.get(0); //Access of vector, get(i), from any index i is O(1)   
    }
    //Just returns the value at index i without modifying the heap 
    @Override
    public T get(int i) { 
        if (m_heap.isEmpty()) return null;
	return m_heap.get(i); //Access of vector, get(i), from any index i is O(1)   
    }
    //Just puts this value at index i, and returns the old value at index i, 
    //without modifying the rest of the heap 
    @Override
    public T set(int i, T val) { return m_heap.set(i, val); }
    //Remove top, heapify and then return old top
    @Override
    public T removeTop() { 
        if (m_heap.isEmpty()) return null;
        T top = m_heap.get(0); //Access of ArrayList, get(i), from any index i is O(1)  
	swapElements(0, m_heap.size() - 1); //Put last element on top
	m_heap.remove(m_heap.size() - 1); //Remove LAST index is O(1) 
	//Swap down with the largest child until it is bigger than its largest child
	int i = 0;
	int largestchild = largestChild(i, m_heap.size());
	while ((largestchild > 0)&&(largestchild < m_heap.size())&&
               (m_heap.get(i).compareTo(m_heap.get(largestchild)) < 0)) {
            swapElements(i, largestchild);        //swap values
            i = largestchild;                     //go down to child
            largestchild = largestChild(i, m_heap.size());       //find new largest child
        }
	return top; //return old top, which was the biggest number in the heap before it was removed
    }
    //Add element as last and then move up as long as it is bigger than its parent 
    @Override
    public void addElement(T val) {
        m_heap.add(val);
	int i = m_heap.size() - 1;
	int parent = parent(i);
	while ((m_heap.get(i).compareTo(m_heap.get(parent)) > 0)&&(i > 0)) {
            swapElements(i, parent);
            i = parent;
            parent = parent(i);
	}
    }
}
